\documentclass[paper=a4, fontsize=12pt]{scrartcl}
\newcommand{\bfvec}[1]{\mbox{\boldmath$#1$}}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{amssymb}
\usepackage{charter}
\usepackage[top=0.75in, bottom=1in, left=0.5in, right=0.5in]{geometry} 
\usepackage{amsmath}
\title{	
\normalfont \normalsize 
\textsc{Shanghai Jiaotong University, Zhiyuan College} \\ [25pt]
\huge Homework 5 \\
}
\author{Feng Shi}
\date{\normalsize\today}
\begin{document}
\maketitle

\begin{enumerate} %begin of questions
\item[Ex 3.19]
{\Large Solution}

Since all $x_{i}$ are stastically independent. the expected value of \bfvec{x}
$$E(\bfvec{x})=E(\sum_{i=1}^{n}x_{i})=\sum_{i=1}^{n}E(x_{i})=\frac{d}{2}$$
and the variance of \bfvec{x}
\begin{align*}
\sigma^{2}(\bfvec{x})&=E((\bfvec{x}-\frac{d}{2})^{2}) \\
&=E(\bfvec{x}^2)-E^{2}(\bfvec{x}) \\
&=E(\sum_{i=1}^{n}x_{i}^2+\sum_{i=1}^{n}\sum_{j=1,j\neq i}^{n}x_{i}x_{j})-\frac{d^2}{4}
\end{align*}
Because $x_{i}$ is indicator variable and is identically distributed, $E(x_{i}^2)=E(x_{i})$.

And $E(x_{i}x_{j})=\frac{1}{4}$, so
$$\sigma^{2}(\bfvec{x})=\frac{n}{2}+\frac{1}{4}\cdot 2\cdot \frac{n(n-1)}{2}-\frac{n^2}{4}=\frac{n}{4}$$
By Chebyshev's inequality,
\begin{align*}
Prob\big( \bfvec{x}=0 \big)&\leq Prob\big( |\bfvec{x}-E(\bfvec{x})|\geq E(\bfvec{x}) \big) \\
&\leq \frac{\sigma(\bfvec{x})}{E^2(\bfvec{x})}=\frac{\sqrt{\frac{n}{4}}}{(\frac{n}{2})^2} \\
&=\frac{1}{8n^\frac{3}{2}}\to 0
\end{align*}
\vspace{20pt}
\newpage
\item[Ex 3.30]
{\Large Solution:}

\begin{enumerate}
\item[-]
{\large Define increasing property}

\bfvec{Q} is an increasing property of $N(n,p)$ i.f.f. it satisfies:

if $N_{1}$ has property \bfvec{Q} then $N_{2}$ obtained by including integers from 
$\lbrace 1,2,...,n \rbrace$ also has property \bfvec{Q}.
\vspace{20pt}

\item[-]
{\large Prove every increasing property of $N(n,p)$ has a threshold}

\textbf{Lemma 1.} \textsl{If \bfvec{Q} is an increasing property and $0\leq p\leq q\leq 1$,
then the probablity that $N(n,p)$ has property \bfvec{Q} is less than or equal to 
the probablity that $N(n,q)$ has property \bfvec{Q}.}

\textbf{Proof:} (of lemma 1.)

Similar to the proof of \emph{Lemma 3.18} on the textbook. 
First generate $N(n,p)$. Then independently generate $N(n,\frac{q-p}{1-p})$ and take
the union by putting in an integer from $\lbrace 1,2,...,n \rbrace$ if either of the
two subsets has the integer. Call the resulting subset $H$. 
$H$ has the same distribution as $N(n,q)$ because the probablity that an integer is
in $H$ is $p+(1-p)\frac{q-p}{1-p}=q$ and the components of $H$ are independent. 
The lemma follows since whenever $N(n,p)$ has the property \bfvec{Q}, H also has
the property \bfvec{Q}.
\vspace{10pt}

\textbf{Lemma 2.} \textsl{If $N(n,q)$ is a $m-$fold replication of N(n,p), 
then there are inequalities below}
$$Prob\big( N(n,q) \ does \ not \ have \ \bfvec{Q} \big)\leq
	\bigg(Prob\big( N(n,p) \ does \ not \ have \ \bfvec{Q} \big)\bigg)^{m}$$
$$Prob\big( N(n,q) \ has \ \bfvec{Q} \big)\leq
	Prob\big( N(n,mp) \ has \ \bfvec{Q} \big)$$
$$Prob\big( N(n,mp) \ does \ not \ have \ \bfvec{Q} \big)\leq
	Prob\big( N(n,q) \ does \ not \ have \ \bfvec{Q} \big)$$
$$Prob\big( N(n,mp) \ does \ not \ have \ \bfvec{Q}\leq
	\bigg(Prob\big( N(n,p) \ does \ not \ have \ \bfvec{Q} \big)\bigg)^{m}$$

\textbf{Proof:} (of lemma 2.) 

$q=q-(1-p)^{m}\leq 1-(1-mp)=mp$ by Bernoulli inequality.

The proof is same as those on the textbook.
\vspace{10pt}

\textbf{Lemma 3.} $\forall\varepsilon \in (0,\frac{1}{2})$, 
take $m$ such that $(1-\varepsilon)^m \leq \varepsilon$.
Then
$$P_{1-\varepsilon}<mP_{\varepsilon}$$
where $P_{1-\varepsilon}$ is the probability $P$ satisfying
$$Prob\big( N(n,P) \ has \ \bfvec{Q}\big)=1-\varepsilon$$
and $P_{\varepsilon}$ defined similarly.

\textbf{Proof:} (of lemma 3.)
Let $N(n,q)$ be the $m-$fold replication of $N(n,P_{\varepsilon})$.
Then by \textsl{lemma 2} we have 
$$Prob\big( N(n,mP_{\varepsilon}) \ has \ \bfvec{Q} \big)
	\geq Prob\big( N(n,q) \ has \ \bfvec{Q}\big)
	\geq 1-\varepsilon$$
And by the increasing property of \bfvec{Q} we have
	$$mP_{\varepsilon}\geq P_{1-\varepsilon}$$

\vspace{10pt}

\textbf{Theorem} Every increasing property \bfvec{Q} of $N(n,p)$ has a threshold.
$P_{1/2}$ is a threshold where $P_{1/2}$ stands for the probablity satisfying
$$Prob\big( N(n,P_{1/2}) \ has \ \bfvec{Q} \big)=\frac{1}{2}$$

\textbf{Proof:} (of the theorem)
\begin{enumerate}
\item[-] {\large \textbf{Solution 1.} \textsl{(simple one)}}
\begin{enumerate}
\item[i.]
$\forall$ $\bar{p}(n)=o(P_{1/2})$, that is,
$\lim_{n \to \infty} \frac{\bar{p}(n)}{P_{1/2}}=0$, we prove that
$$Prob\big( N(n,\bar{p}(n)) \ has \ \bfvec{Q}\big)\to 0 \ as \ n\to\infty$$

Proof by contradiction:

Suppose $Prob\big( N(n,\bar{p}(n) \ has \ \bfvec{Q})\big)\to\epsilon$ 
where $\epsilon\in(0,\frac{1}{2})$. Then by $\varepsilon-\Delta$ definition of
limitation, we have
	$$\exists N_0\in \mathbb{N},\varepsilon\in (0,\frac{1}{2}) \ s.t. \ 
	\forall N>N_0, \ Prob\big( N(n,\bar{p}(n) \ has \ \bfvec{Q}\big)>\varepsilon$$

Take $m \ s.t. \ (1-\varepsilon)<\varepsilon^m$. Then by \textsl{lemma 3} we have
$$P_{1-\varepsilon}<mP_\varepsilon$$

Because \bfvec{Q} is an increasing property.
$$P_{1/2}<P_{1-\varepsilon} \ , \ P_\varepsilon<\bar{p}(n)$$

So
$$P_{1/2}<P_{1-\varepsilon}<mP_{\varepsilon}<m\bar{p}(n)$$

Because $m$ is only related to $\varepsilon$ but not $n$, this yields 
$$\lim_{n\to\infty} \frac{\bar{p}(n)}{P_{1/2}}>0$$
which contradicts $\bar{p}(n)=o(P_{1/2})$, so
$$Prob\big( N(n,\bar{p}(n)) \ has \ \bfvec{Q}\big)\to 0 \ as \ n\to\infty$$

\item[ii.]
$\forall$ $\hat{p}(n)=\Omega(P_{1/2})$, that is,
$\lim_{n \to \infty} \frac{\hat{p}(n)}{P_{1/2}}=\infty$, we prove that
$$Prob\big( N(n,\hat{p}(n)) \ has \ \bfvec{Q}\big)\to 1 \ as \ n\to\infty$$

Proof by contradiction:

Suppose	$Prob\big( N(n,\hat{p}(n) \ has \ \bfvec{Q})\big)\to 1-\epsilon$  
where $\epsilon\in(0,\frac{1}{2})$. Then by $\varepsilon-\Delta$ definition of
limitation, we have
	$$\exists N_0\in \mathbb{N},\varepsilon\in (0,\frac{1}{2}) \ s.t. \ 
	\forall N>N_0, \ Prob\big( N(n,\hat{p}(n) \ has \ \bfvec{Q}\big)<1-\varepsilon$$
Then similarly by \textsl{lemma 3} and increasing property of \bfvec{Q}, we have
$$\hat{p}(n)<P_{1-\varepsilon}<mP_\varepsilon<mP_{1/2}$$
which contradicts with $\hat{p}(n)=\Omega(P_{1/2})$, so
$$Prob\big( N(n,\hat{p}(n)) \ has \ \bfvec{Q}\big)\to 1 \ as \ n\to\infty$$
\vspace{10pt}
By \textsl{i.} and \textsl{ii.} we can conclude that $P_{1/2}$ is a threshold for
increasing property \bfvec{Q} of $N(n,p)$.
\end{enumerate} %end of 2 conditions
\vspace{20pt}

\item[-] {\large \textbf{Solution 2.} \textsl{(similar to textbook)}}
\begin{enumerate}
\item[i.] Prove that if any $p_1(n) \ s.t. \ \lim_{n\to \infty}\frac{p_1(n)}{p(n)}=0$,
then $N(n,p_1)$ almost surely doesn't have property \bfvec{Q}.

Similar to textbook.

\item[ii.] Prove that if any $p_2(n) \ s.t. \ \lim_{n\to\infty}\frac{p_2(n)}{p(n)}=\infty$,
then $N(n,p_2)$ almost surely has property \bfvec{Q}.

Prove by contradiction: assume that $Prob\big( N(n,p_2) \ has \ \bfvec{Q}\big)$ does not
converge to 1 as $n\to\infty$, then
$$\exists \varepsilon>0, \ \forall N\in\mathbb{N}, \ \exists n>N, 
\ Prob\big( N(n,p_2(n)) \ has \ \bfvec{q}\big)\leq 1-\varepsilon$$
Take $m=\lceil log_\frac{1}{2}\varepsilon\rceil$ and let $N(n,q)$ be the $m-$fold replication
of $N(n,p)$. Then by \textsl{lemma 2}
\begin{align*}
Prob\big( N(n,mp) \ has \ \bfvec{Q}\big) &\geq Prob\big( N(n,q) \ has \ \bfvec{Q}\big) \\
	&\geq 1-\bigg( Prob\big( N(n,p) \ does \ not \ have \ \bfvec{Q}\big) \bigg)^m \\
	&=1-\big(\frac{1}{2}\big)^m \\
	&\geq 1-\varepsilon
\end{align*}
And by monotonic property of \bfvec{Q} we have
$$mp>p_2$$ 
for infinitely often which contradicts with the condition that 
$\lim_{n\to\infty}\frac{p_2(n)}{p(n)}=\infty$, thus finishes the proof.
\end{enumerate} %end of solution 2
\end{enumerate} %end of solution 1,2
\vspace{30pt}
{\large P.S.} The proof of \textsl{theorem 3.19} (which is similar to \textsl{solution 2})
didn't include \textsl{lemma 3} above.
The conclusion of \textsl{lemma 3} is very symmetric and so is \textsl{solution 1}.
And calculation in \textsl{solution 1} is much simpler. So I think \textsl{lemma 3}
is useful. Futher more, I believe that \textsl{lemma 3} itself implies the existence of
a threshold, which I will try to prove later.
\end{enumerate} %end of ex 3.30


\end{enumerate} %end of questions
\end{document}

